#include<bits/stdc++.h>
using namespace std;
int C,T,n,m,ans,u[11004],v[11004];
bool e[10][10];
int dis[10][10],mx,cnt;
inline void sol(){
	for(int i=1;i<=n;++i)
	for(int j=1;j<=n;++j)
		dis[i][j]=(e[i][j]?1:(i==j?0:1e8));
	for(int k=1;k<=n;++k)
	for(int i=1;i<=n;++i)
	for(int j=1;j<=n;++j)
		dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
	int sum=0;
	for(int i=1;i<=m;++i) sum-=dis[u[i]][v[i]];
	if(sum>mx) mx=sum,cnt=1;
	else if(sum==mx) ++cnt;
}
void dfs(int x,int p,int v){
	if(x==m) return sol(),void();
	if(x+n-v+(n-p)*(n-p-1)/2<m-1) return;
	for(int i=p;i<=n;++i)
	for(int j=(i==p?v+1:i+1);j<=n;++j)
		e[i][j]=e[j][i]=1,dfs(x+1,i,j),e[i][j]=e[j][i]=0;
}
int main(){
	freopen("oi.in","r",stdin);
	freopen("oi.out","w",stdout);
	cin>>C>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=m;++i) cin>>u[i]>>v[i];
		if(n<=5){
			mx=-1e9,cnt=0;
			dfs(1,1,1);
			cout<<mx<<' '<<cnt<<'\n';
		}else cout<<-2*(n-1)<<" 0\n";
	}
	return 0;
}


